#include <stdio.h>

/*
 * Find two element that their total value is a given integer
 * Here, wo have some assumes: the input array has been descently sorted; all the elements are positive integer
 * (C) 2012 Sheng Yi
 */

// First, a ugly way is given: derectly traversal
bool find_sum(int a[], int len, int sum);

bool find_sum(int a[], int len, int sum)
{
	int i, j;
	bool find = false;
	for (i = 0; i < len; ++i)
	{
		dif = sum - a[i];
		for (j = 0; j < len; j++)
		{
			if (a[j] == dif)
			{
				find = true;
				printf("Find %d = %d + %d\n", sum, a[i], a[j]);
			}
		}
	}
}

/*
 * A elegant way to finish.
 */
void print_sum(int a[], int len, int sum)
{
	int i, j, res;
	for (i = 0, j = len - 1; i < j; )
	{
		res = a[i] +  a[j];
		if (res == sum)
		{
			print("Find: %d = %d + %d\n", sum, a[i], a[j]);
			i++;
			j--;
		}
		else if (res > sum)
			j--;
		else
			i++;
	}
}
